/*
 *  linux/mm/memory.c
 *
 *  (C) 1991  Linus Torvalds
 */

/*
 * demand-loading started 01.12.91 - seems it is high on the list of
 * things wanted, and it should be easy to implement. - Linus
 */

/*
 * Ok, demand-loading was easy, shared pages a little bit tricker. Shared
 * pages started 02.12.91, seems to work. - Linus.
 *
 * Tested sharing by executing about 30 /bin/sh: under the old kernel it
 * would have taken more than the 6M I have free, but it worked well as
 * far as I could see.
 *
 * Also corrected some "invalidate()"s - I wasn't doing enough of them.
 */

#include <signal.h>

#include <asm/system.h>

#include <linux/sched.h>
#include <linux/head.h>
#include <linux/kernel.h>

volatile void do_exit(long code);//进程退出处理函数,定义在kernel/exit.c中

static inline volatile void oom(void)
{
	printk("out of memory\n\r");
	do_exit(SIGSEGV);//资源暂时不可用
}

#define invalidate() \
__asm__("movl %%eax,%%cr3"::"a" (0))//刷新页变换高速缓冲。在修改过页表信息之后，需要刷新高速缓冲区。这里采用重新加载页目录基址寄存器cr3的方法来刷新

/* these are not to be changed without changing head.s etc */
#define LOW_MEM 0x100000//内存低端，1MB
#define PAGING_MEMORY (15*1024*1024)//分页内存15MB
#define PAGING_PAGES (PAGING_MEMORY>>12)//分页后的物理内存页数
#define MAP_NR(addr) (((addr)-LOW_MEM)>>12)//指定内存地址映射为页号
#define USED 100//页面被占用标志

#define CODE_SPACE(addr) ((((addr)+4095)&~4095) < \
current->start_code + current->end_code)//用于判断给定地址是否位于进程的代码段中

static long HIGH_MEMORY = 0;//存放实际物理内存最高端地址

#define copy_page(from,to) \
__asm__("cld ; rep ; movsl"::"S" (from),"D" (to),"c" (1024)) //复制一页内存

static unsigned char mem_map [ PAGING_PAGES ] = {0,};

/*
 * Get physical address of first (actually last :-) free page, and mark it
 * used. If no free pages left, return 0.
 */
unsigned long get_free_page(void)
{
register unsigned long __res asm("ax");

__asm__("std ; repne ; scasb\n\t"
	"jne 1f\n\t"
	"movb $1,1(%%edi)\n\t"
	"sall $12,%%ecx\n\t"
	"addl %2,%%ecx\n\t"
	"movl %%ecx,%%edx\n\t"
	"movl $1024,%%ecx\n\t"
	"leal 4092(%%edx),%%edi\n\t"
	"rep ; stosl\n\t"
	"movl %%edx,%%eax\n"
	"1:"
	:"=a" (__res)
	:"0" (0),"i" (LOW_MEM),"c" (PAGING_PAGES),
	"D" (mem_map+PAGING_PAGES-1)
	);
return __res;//返回空闲页面地址，如果无空闲则返回0
}

/*
 * Free a page of memory at physical address 'addr'. Used by
 * 'free_page_tables()'
 */
void free_page(unsigned long addr)
{
	if (addr < LOW_MEM) return;
	if (addr >= HIGH_MEMORY)
		panic("trying to free nonexistent page");
	addr -= LOW_MEM;
	addr >>= 12;
	if (mem_map[addr]--) return;
	mem_map[addr]=0;
	panic("trying to free free page");
}

/*
 * This function frees a continuos block of page tables, as needed
 * by 'exit()'. As does copy_page_tables(), this handles only 4Mb blocks.
 */
int free_page_tables(unsigned long from,unsigned long size)//from是起始基地址，size是要释放的内存块的长度
{
	unsigned long *pg_table;
	unsigned long * dir, nr;

	if (from & 0x3fffff)//以4MB为限。因为一个页表最多也就记录1K个页，共计1K * 4K = 4MB大小的内存。每个与、page_table的指向的第一个物理内存的地址的低22位必然全为0
		panic("free_page_tables called with wrong alignment");
	if (!from)//from不可用为0
		panic("Trying to free up swapper memory space");
	size = (size + 0x3fffff) >> 22;//22是4MB。此时size表示的是需要释放多少个page_table
	dir = (unsigned long *) ((from>>20) & 0xffc); /* _pg_dir = 0 */ //因为page_table中的每个项占4个字节，因此只需要右移20bit
	for ( ; size-->0 ; dir++) {
		if (!(1 & *dir))//每个目录项的最低位是P为。如果该目录项无效，则继续
			continue;
		pg_table = (unsigned long *) (0xfffff000 & *dir);//取出页目录项中的页表地址
		for (nr=0 ; nr<1024 ; nr++) {//每个页表有1024个页表项
			if (1 & *pg_table)//如果页表有效，则释放对应内存页
				free_page(0xfffff000 & *pg_table);
			*pg_table = 0;//该页表项内容清零
			pg_table++;//移动到下一个页表项
		}
		free_page(0xfffff000 & *dir);//释放该页表所占内存页面
		*dir = 0;//相应也目录项清零
	}
	invalidate();
	return 0;
}

/*
 *  Well, here is one of the most complicated functions in mm. It
 * copies a range of linerar addresses by copying only the pages.
 * Let's hope this is bug-free, 'cause this one I don't want to debug :-)
 *
 * Note! We don't copy just any chunks of memory - addresses have to
 * be divisible by 4Mb (one page-directory entry), as this makes the
 * function easier. It's used only by fork anyway.
 *
 * NOTE 2!! When from==0 we are copying kernel space for the first
 * fork(). Then we DONT want to copy a full page-directory entry, as
 * that would lead to some serious memory waste - we just copy the
 * first 160 pages - 640kB. Even that is more than we need, but it
 * doesn't take any more memory - we don't copy-on-write in the low
 * 1 Mb-range, so the pages can be shared with the kernel. Thus the
 * special case for nr=xxxx.
 */
int copy_page_tables(unsigned long from,unsigned long to,long size)//该函数只会被fork调用
{
	unsigned long * from_page_table;
	unsigned long * to_page_table;
	unsigned long this_page;
	unsigned long * from_dir, * to_dir;
	unsigned long nr;

	if ((from&0x3fffff) || (to&0x3fffff))//from和to的地址都必须是在4MB内存的边界地址上
		panic("copy_page_tables called with wrong alignment");
	from_dir = (unsigned long *) ((from>>20) & 0xffc); /* _pg_dir = 0 */
	to_dir = (unsigned long *) ((to>>20) & 0xffc);
	size = ((unsigned) (size+0x3fffff)) >> 22;//一共copy多少个page_table
	for( ; size-->0 ; from_dir++,to_dir++) {
		if (1 & *to_dir)
			panic("copy_page_tables: already exist");
		if (!(1 & *from_dir))
			continue;
		from_page_table = (unsigned long *) (0xfffff000 & *from_dir);//取页表地址
		if (!(to_page_table = (unsigned long *) get_free_page()))
			return -1;	/* Out of memory, see freeing */
		*to_dir = ((unsigned long) to_page_table) | 7;
		nr = (from==0)?0xA0:1024;//如果是拷贝内核空间就拷贝前160个页面，否则就拷贝1024个页面
		for ( ; nr-- > 0 ; from_page_table++,to_page_table++) {
			this_page = *from_page_table;//取源页表项内容
			if (!(1 & this_page))
				continue;
			this_page &= ~2;//将页表项中的R/W标志置为0，即设置为已读。copy on write前的准备
			*to_page_table = this_page;//这是copy on write的操作。即实际上不拷贝物理内存页，而只是指向相同的页。当对页进行修改时才会复制页面
			if (this_page > LOW_MEM) {//如果在1MB以上，则需要设置mem_map数组，增加引用次数
				*from_page_table = this_page;//令源页表项也是只读的
				this_page -= LOW_MEM;
				this_page >>= 12;
				mem_map[this_page]++;
			}
		}
	}
	invalidate();
	return 0;
}

/*
 * This function puts a page in memory at the wanted address.
 * It returns the physical address of the page gotten, 0 if
 * out of memory (either when trying to access page-table or
 * page.)
 */
unsigned long put_page(unsigned long page,unsigned long address)//把物理内存页面映射到指定的线性地址，或者说是把线性空间中指定地址address处的页面映射到主内存区页面page上
{//实现该功能的主要工作是在相关页目录项和页表项中设置指定页面的信息。在处理缺页异常C函数do_no_page()中会调用此函数。参数page是分配的主内存区中某一页面的指针
	unsigned long tmp, *page_table;

/* NOTE !!! This uses the fact that _pg_dir=0 */

	if (page < LOW_MEM || page >= HIGH_MEMORY)//如果申请的页面地址不在可支持的内存范围内则报错
		printk("Trying to put page %p at %p\n",page,address);
	if (mem_map[(page-LOW_MEM)>>12] != 1)//如果申请的页面在mem_map中没有置位则报错
		printk("mem_map disagrees with %p at %p\n",page,address);
	page_table = (unsigned long *) ((address>>20) & 0xffc);//计算指定地址在页目录表中对应的目录项指针
	if ((*page_table)&1)//如果指定的页表在内存中
		page_table = (unsigned long *) (0xfffff000 & *page_table);//提取页表地址
	else {//否则申请一个空闲页面给页表用
		if (!(tmp=get_free_page()))
			return 0;
		*page_table = tmp|7;
		page_table = (unsigned long *) tmp;
	}
	page_table[(address>>12) & 0x3ff] = page | 7;//把物理地址page的地址填入表项，同时置位最后3个标志
/* no need for invalidate *///由于缺页引起的对页表的修改时，不需要刷新CPU的页变换缓冲，即使页表项中标志P被从0修改成1.因为无效页项不会被缓冲，因此当修改了一个无效的页表时不需要刷新。
	return page;
}
//取消写保护。内核在创建进程时，父子进程共享代码和数据的内存页面，并且所有这些页面均被设置为只读。当进程需要写时，CPU会检测页面并产生页面写保护异常。于是在这个函数中内核会首先判断要写的页面是否被共享，若被共享则复制页面后再写并取消共享；否则直接写入即可
void un_wp_page(unsigned long * table_entry)//输入为页表项指针
{
	unsigned long old_page,new_page;

	old_page = 0xfffff000 & *table_entry;//提取页地址
	if (old_page >= LOW_MEM && mem_map[MAP_NR(old_page)]==1) {//未被共享。因为页面仅被引用一次
		*table_entry |= 2;//设置可写标志
		invalidate();
		return;
	}
	if (!(new_page=get_free_page()))
		oom();//out of memory
	if (old_page >= LOW_MEM)
		mem_map[MAP_NR(old_page)]--;//减少一次引用
	*table_entry = new_page | 7;//设置页表指向新地址，且设置为可写
	invalidate();//刷新高速缓存
	copy_page(old_page,new_page);//复制页面数据
}	

/*
 * This routine handles present pages, when users try to write
 * to a shared page. It is done by copying the page to a new address
 * and decrementing the shared-page counter for the old page.
 *
 * If it's in code space we exit with a segment error.
 *///执行共享页面的写保护页面处理。这是页异常中断处理过程中调用C函数，会在page.s中被调用。写共享页面时，需要复制页面
void do_wp_page(unsigned long error_code,unsigned long address)//error_code是CPU自动产生的，address是线性地址
{
#if 0
/* we cannot do this yet: the estdio library writes to code space */
/* stupid, stupid. I really want the libc.a from GNU */
	if (CODE_SPACE(address))//如果地址位于代码空间，则终止执行程序
		do_exit(SIGSEGV);
#endif//((address>>10) & 0xffc) 计算得到指定地址的页面在页表中的偏移值
	un_wp_page((unsigned long *)//((address>>20) &0xffc)计算得到指定地址在页目录项指针
		(((address>>10) & 0xffc) + (0xfffff000 &//(0xfffff000 &*((unsigned long *) ((address>>20) &0xffc))) 计算得到页目录项中页表的地址值
		*((unsigned long *) ((address>>20) &0xffc)))));
// 指定地址的页面在页表中的偏移值 + 页目录项中页表的地址值即为页面在页表中的页表项指针
}
// 写页面验证。若页面不可写，则复制页面
void write_verify(unsigned long address)
{
	unsigned long page;

	if (!( (page = *((unsigned long *) ((address>>20) & 0xffc)) )&1))//page此时值为页目录项，若&1之后判等通过这说明该目录项是有效的
		return;
	page &= 0xfffff000;//取页表地址
	page += ((address>>10) & 0xffc);//取线性地址在页表中的偏移值
	if ((3 & *(unsigned long *) page) == 1)  /* non-writeable, present */
		un_wp_page((unsigned long *) page);
	return;
}
// 为线性地址申请一个空页面。并将页面映射到指定的线性地址
void get_empty_page(unsigned long address)
{
	unsigned long tmp;

	if (!(tmp=get_free_page()) || !put_page(tmp,address)) {
		free_page(tmp);		/* 0 is ok - ignored */
		oom();
	}
}

/*
 * try_to_share() checks the page at address "address" in the task "p",
 * to see if it exists, and if it is clean. If so, share it with the current
 * task.
 *
 * NOTE! This assumes we have checked that p != current, and that they
 * share the same executable.
 */
static int try_to_share(unsigned long address, struct task_struct * p)//尝试对当前进程指定地址处的页面与p进程address处的页面进行共享处理
{//如果p进程的address处的页面存在并且没有被修改过的话，就让当前进程与p进程共享之。返回值1表示成功，0表示失败
	unsigned long from;
	unsigned long to;
	unsigned long from_page;
	unsigned long to_page;
	unsigned long phys_addr;

	from_page = to_page = ((address>>20) & 0xffc);//指定内存地址的页目录项
	from_page += ((p->start_code>>20) & 0xffc);//计算进程p的代码起始地址所对应的页目录项 //TODO 这里为啥是相加
	to_page += ((current->start_code>>20) & 0xffc);//计算当前进程的代码起始地址对应的页目录项地址
/* is there a page-directory at from? */
	from = *(unsigned long *) from_page;//取页目录项内容,下面判断该目录项是否有效
	if (!(from & 1))
		return 0;
	from &= 0xfffff000;//取页表地址
	from_page = from + ((address>>10) & 0xffc);//页表地址 + 在页表中的偏移值就是页表项
	phys_addr = *(unsigned long *) from_page;//取页表项
/* is the page clean and present? */
	if ((phys_addr & 0x41) != 0x01)//对应也表中的dirty和present标志，如果页面不干净或者不存在则返回
		return 0;
	phys_addr &= 0xfffff000;//取页面地址
	if (phys_addr >= HIGH_MEMORY || phys_addr < LOW_MEM)
		return 0;
	to = *(unsigned long *) to_page;//取页目录项内容
	if (!(to & 1)) {//该页目录项无效,那么下面就获取一个新的页面以建立页表
		if ((to = get_free_page()))
			*(unsigned long *) to_page = to | 7;//修改页目录项
		else
			oom();
	}
	to &= 0xfffff000;//取页表地址
	to_page = to + ((address>>10) & 0xffc);//计算线性地址对应的页表项
	if (1 & *(unsigned long *) to_page)//如果页表项有效则to_page已经存在
		panic("try_to_share: to_page already exists");
/* share them: write-protect */
	*(unsigned long *) from_page &= ~2;//源页面置为只读
	*(unsigned long *) to_page = *(unsigned long *) from_page;//将页表项设置成与原页表项相同
	invalidate();
	phys_addr -= LOW_MEM;
	phys_addr >>= 12;
	mem_map[phys_addr]++;
	return 1;
}

/*
 * share_page() tries to find a process that could share a page with
 * the current one. Address is the address of the wanted page relative
 * to the current data space.
 *
 * We first check if it is at all feasible by checking executable->i_count.
 * It should be >1 if there are other tasks sharing this inode.
 */
static int share_page(unsigned long address)//共享页面。在缺页处理时看看能否共享页面。1 - 成功， 0 - 失败
{//注意这个address是进程中线性地址相对于进程基址的偏移长度值
	struct task_struct ** p;
	// executable 指向进程正在执行程序在内存中的i节点。根据i节点的引用次数i_count可以进行判断是否有另一个进程也在执行同一个可执行文件
	if (!current->executable)//struct task_struct *current = &(init_task.task); // 定义在<linux/kernel>中
		return 0;
	if (current->executable->i_count < 2)
		return 0;
	for (p = &LAST_TASK ; p > &FIRST_TASK ; --p) {//#define FIRST_TASK task[0] // #define LAST_TASK task[NR_TASKS-1] //定义在<linux/sched.h>
		if (!*p)
			continue;
		if (current == *p)
			continue;
		if ((*p)->executable != current->executable)
			continue;
		if (try_to_share(address,*p))//有两个进程同时执行同一个可执行程序，尝试对address对应的页面进行共享
			return 1;
	}
	return 0;
}
//处理缺页异常的程序。在page.s中被调用。
void do_no_page(unsigned long error_code,unsigned long address)//error_code是CPU产生的，address是页面线性地址
{
	int nr[4];
	unsigned long tmp;
	unsigned long page;
	int block,i;

	address &= 0xfffff000;//取页面地址
	tmp = address - current->start_code;//计算线性地址在进程空间中相对于进程基址的偏移长度值
	if (!current->executable || tmp >= current->end_data) {//若executable为空或者指定地址超出代码+数据长度则需要申请物理空间，映射到指定线性地址
		get_empty_page(address);
		return;
	}
	if (share_page(tmp))
		return;
	if (!(page = get_free_page()))
		oom();
/* remember that 1 block is used for header */
	block = 1 + tmp/BLOCK_SIZE; // #define BLOCK_SIZE 1024 // 定义在<linux/fs.h>
	for (i=0 ; i<4 ; block++,i++)
		nr[i] = bmap(current->executable,block);//根据i节点信息，取数据块在设备上对应的逻辑块号
	bread_page(page,current->executable->i_dev,nr);//读设备上一个页面的数据（4个逻辑块）到指定物理地址page处
	i = tmp + 4096 - current->end_data;//在增加了一页内存之后，改页内存的部分可能会超过进程的end_data位置。下面的循环是对物理页面超出的部分进行清零操作
	tmp = page + 4096;
	while (i-- > 0) {
		tmp--;
		*(char *)tmp = 0;
	}
	if (put_page(page,address))//将物理页面映射到线性地址
		return;
	free_page(page);
	oom();
}
// 物理内存初始化。 
void mem_init(long start_mem, long end_mem)
{
	int i;

	HIGH_MEMORY = end_mem;
	for (i=0 ; i<PAGING_PAGES ; i++)
		mem_map[i] = USED;//将所有页面设置为已占用
	i = MAP_NR(start_mem);//计算可使用的起始内存的页面号
	end_mem -= start_mem;//计算总共可使用的内存的大小
	end_mem >>= 12;
	while (end_mem-->0)//将可用页面设置为0
		mem_map[i++]=0;
}

void calc_mem(void)
{
	int i,j,k,free=0;
	long * pg_tbl;

	for(i=0 ; i<PAGING_PAGES ; i++)
		if (!mem_map[i]) free++;
	printk("%d pages free (of %d)\n\r",free,PAGING_PAGES);
	for(i=2 ; i<1024 ; i++) {
		if (1&pg_dir[i]) {//如果页目录有效
			pg_tbl=(long *) (0xfffff000 & pg_dir[i]);//取页表地址
			for(j=k=0 ; j<1024 ; j++)
				if (pg_tbl[j]&1)//如果页表项有效
					k++;
			printk("Pg-dir[%d] uses %d pages\n",i,k);
		}
	}
}
